package 剑指offer;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @description:
 * @author: ywk
 * @date: 2021-03-02
 */
public class 设计getMin功能的栈 {


    /**
     * 有三种操作种类，op1表示push，op2表示pop，op3表示getMin。你需要返回和op3出现次数一样多的数组，表示每次getMin的答案
     *
     * 1<=操作总数<=1000000
     * -1000000<=每个操作数<=1000000
     * 数据保证没有不合法的操作
     * @param op
     * @return
     */

    public static int[] getMinStack2(int[][] op) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        //添加额外的存储空间作为作为最小栈
        Stack<Integer> minStack = new Stack<>();
        ArrayList<Integer> ans = new ArrayList<>();
        for (int[] opr : op) {
            if (opr[0] == 1) {
                stack.push(opr[1]);
                if (minStack.isEmpty() || opr[1] <= minStack.peek())
                    minStack.push(opr[1]);
            } else if (opr[0] == 2) {
                if (minStack.peek().equals((stack.peek())))
                    minStack.pop();
                stack.pop();
            } else if (opr[0] == 3)
                ans.add(minStack.peek());
        }
        int[] ret = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++)
            ret[i] = ans.get(i);
        return ret;

    }
    public static int[] getMinStack(int[][] op) {
        // write code here
        List<Integer> result = new ArrayList<>();
        List<Integer> stack = new ArrayList<>();
        for (int i = 0; i < op.length; i++) {
            switch (op[i][0]) {
                //1.push
                case 1:
                    stack.add(op[i][1]);
                    break;
                //2.pop
                case 2:
                    stack.remove(stack.size()-1);
                    break;
                //3.getMin
                case 3:
                    int min = stack.get(stack.size()-1);
                    for (int j = 0; j < stack.size(); j++) {
                        if (stack.get(j) < min) {
                            min = stack.get(j);
                        }
                    }
                    result.add(min);
                    break;
            }
        }
        int[] arr = new int[result.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = result.get(i);
        }
        return arr;
    }
}
